#include <iostream>

using namespace std;

#define N 100

void PrintArray(int* a, int n)
{
    for (int i = 0; i < n; ++i)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}

//向下调整算法 前提：左右子树都是小堆 可以把最 小/大 的数
void AdjustDwon(int* a, int n, int root)
{
	int parent = root;
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] > a[child])	//选择大小堆  
		{
			child += 1;
		}

		if (a[child] > a[parent])
		{
			swap(a[child], a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else break;
	}
}

void HeapSort(int* a, int n)
{
	//建堆的过程 时间复杂度 O(n)
    for (int i = (n - 1 - 1) / 2; i >= 0; --i)  //从最后一个非叶子节点开始建堆 N / 2
    {
        AdjustDwon(a, n, i);
    }
	//升序 建大堆 再将第一个和最后一个交换，root 左右子树都是大堆 这样子除了root小就可以adjust
	int end = n - 1;
	while (end > 0)
	{
		swap(a[0], a[end]);
		AdjustDwon(a, end, 0);
		end--;
	}
}

int main()
{
	int a[] = { 3, 5, 2, 7, 8, 6, 1, 9, 4, 0 };
	HeapSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
    return 0;
}